Internet Protocol Security, or “IPSec”, described in RFC4301 as published in to December 2005 as a Request for Comments (RFC) by the Internet Engineering Task Force (IETF), requires packets to be processed according to the packet's appropriate security policy. That policy determines the packet disposition, either passed through unmodified, encrypted, or dropped. Data packets need to be mapped to the appropriate policy to determine the packet's disposition.
Policies typically contain a 7-tuple attribute specification (also referred to as a configured policy selector) comprising the source IP address, source IP address mask (or source subnet mask), source port, destination IP address, destination address mask (or destination subnet mask), destination port and the protocol. A policy whose 7-tuple matches the IP packet's source IP address, source port, destination IP address, destination port, and protocol fields (referred to as the 5-tuple) under consideration, is deemed to be a matching policy for that packet.
A specific policy may identify a broad range of IP packets or may identify specific packets by defining IP address ranges, including wild card IP addresses, and IP address masks and by defining the port and/or protocol as wild card value. As such there will generally be more than one policy that matches a packet due to overlapping selectors.
RFC4301 specifies that policies must be ordered so that the appropriate policy for a given data packet can be deterministically found. For aggregation points, there can be thousands of policies, many of which are overlapping policies.
Current implementations for retrieving the appropriate policy include software and hardware assisted approaches. The software approaches include placing the policies in a linked list ordered in some fashion such as from most specific selector specification to the least specific selector specification. The search algorithm then iterates through the list until a match is found or the end of the list reached. For this algorithmic approach, the search time is proportional to the number of policy selectors configured.
Another software approach involves using hash tables. The entire 5-tuple of an IP packet (i.e., source IP address, source port, destination IP address, destination port, and protocol) is fed into a hash function producing a number (hash value) that is used as an index into a table whose entries contain a linked list of potentially matching policies. The policies in that linked list are then examined for a match with the 5-tuple. This algorithm relies on the hash function to significantly reduce the number of policies that need to be considered in the search. This approach tends to be susceptible when overlapping policies exist whereby these policies need to be added to multiple entries in the hash table or processed separately in some other fashion. Generally the better the hash function is in distributing the policies over the range of the array dimension, the longer that function takes to compute the index.
Hardware assisted approaches for policy lookup include using a ternary Content Addressable Memory (CAM) to store the policy index matching the 5-tuple. This provides fast policy lookup. The disadvantage with respect to the software approaches include the cost associated with the CAM and that the CAM is limited in the number of entries it can hold.
Techniques for searching a security policy database (SPD) in a network security environment are known. U.S. Pat. No. 6,347,376 describes an ordering of rules from most specific to least specific then dynamic rules. U.S. Pat. No. 7,392,241 describes splitting SPD into peer based SPDs. U.S. Pat. No. 6,715,081 describes an ordering of rules from most specific to least specific then dynamic rules. U.S. App. Pub. No. 20060074899 describes storing and searching a hierarchy of policies and associations thereof of particular use with IP security policies and security associations. U.S. App. Pub. No. 20050044068 describes splitting an SPD database into smaller peer based SPDs. U.S. App. Pub. No. 20030061507 and U.S. App. Pub. No. 20010042204 describes hash implementations.